package BSQX_Bit;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
class Main{
    static  int t=123;
    public static void  fun1(){
        Main s=new Main();
        s.fun();

    }
    public  void  fun(){
        t=1234;
        fun1();
        this.fun();
        fun();
    }
}

public class BSQX_4_15 {
    public static ArrayList<int[]> path = new ArrayList<>();//搜索所有可能的路径
    public static ArrayList<int[]> best_path = new ArrayList<>();//最短路径
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            path.clear();
            best_path.clear();//每个用例之前，都要清空下路径
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] board = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    board[i][j] = in.nextInt();
                }
            }
            dfs(0,0,board);//深搜+回溯
            for(int[] pathi:best_path){
                System.out.println("(" + pathi[0] + "," + pathi[1] + ")");
            }
        }
    }
    public static void dfs(int i,int j,int[][] board){
        //越界了
        if(i<0 || i>board.length-1 || j<0 || j>board[0].length-1){
            return;
        }
        //撞墙了
        if(board[i][j]==1){
            return;
        }
        //终止条件,找到终点了
        if(i==board.length-1 && j==board[0].length-1){
            path.add(new int[]{board.length-1,board[0].length-1});//添加终点
            if(best_path.size()==0 || path.size()<best_path.size()){//遇到更短的路径
                best_path.clear();//清空之前的路径
                for(int[] path0:path){
                    best_path.add(path0);
                }
            }
            return;
        }
        board[i][j] = 1;//标记走过的点
        path.add(new int[]{i,j});//添加到路径中
        dfs(i-1,j,board);
        dfs(i+1,j,board);
        dfs(i,j-1,board);
        dfs(i,j+1,board);//以i j为中心，上下左右搜索
        board[i][j] = 0;//回溯，恢复到之前的状态
        path.remove(path.size()-1);//回溯，移除最后一个点
    }

   /*static ArrayList<int[]> arrayList=new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m=in.nextInt();
        int n=in.nextInt();

       int[][] arr=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j]=in.nextInt();
            }
        }
        path(arr,0,0);
        for (int i = 0; i < arrayList.size(); i++) {
            int[] ret=arrayList.get(i);
            System.out.println(ret.toString());
        }

    }
    public static void path(int[][] board,int s,int e){

        if (s < 0 || e < 0 || s >= board.length || e >= board[0].length){
            return;
        }
        if (board[s][e] == 1)return;

        path(board,s+1,e);
        path(board,s,e+1);
        path(board,s-1,e);
        path(board,s,e-1);
        arrayList.add(new int[]{s,e});
    }*/


    public int getMost(int[][] board) {
        if ( board == null ||  board.length == 0 || board[0].length == 0) {
            return 0;
        }
        int m= board.length;
        int n=board[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=board[0][0];
        /*构造一个dp数组,里面存放当前的最大值*/
        for (int i = 1; i < m; i++) {
            dp[i][0]=board[i][0]+dp[i-1][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i]=board[0][i]+dp[0][i-1];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j]=board[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
}



